L2-011 玩转二叉树

题目 L2-011 玩转二叉树

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=35;

int in[N],pre[N];

typedef struct BiTNode {

	int val;

	struct BiTNode *lchild,*rchild;

} BiTNode,*BiTree;

BiTree build_Tree_from_PreIn(int in[],int l1,int r1,int pre[],int l2,int r2) {

	if(l1>r1 || l2>r2)	return NULL;

	BiTree root = new BiTNode;

	root->val = pre[l2];

	int tmp;

	for(int i=l1;i<=r1;i++){

		if(in[i]==pre[l2]){

			tmp=i;

			break;

		}

	}

	root->lchild=build_Tree_from_PreIn(in,l1,tmp-1,pre,l2+1,l2+1+tmp-l1-1);

	root->rchild=build_Tree_from_PreIn(in,tmp+1,r1,pre,l2+1+tmp-l1-1+1,r2);

	return root;

}

void print_pre(BiTree root){

	if(root){

		cout<<root->val<<" ";

		print_pre(root->lchild);

		print_pre(root->rchild);

	}

}

void mirror(BiTree root){

	if(!root)	return;

	swap(root->lchild,root->rchild);

	mirror(root->lchild);

	mirror(root->rchild);

}

void bfs(BiTree root){

	if(!root)	return;

	queue<BiTree> q;

	q.push(root);

	bool is_first=true;

	while(q.size()){

		auto tmp=q.front();q.pop();

		if(is_first){

			cout<<tmp->val;

			is_first=false;

		}else{

			cout<<" "<<tmp->val;

		}

		if(tmp->lchild) 	q.push(tmp->lchild);

		if(tmp->rchild) 	q.push(tmp->rchild);

	}

}

int main() {

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n;cin>>n;

	for(int i=0;i<n;i++)	cin>>in[i];

	for(int i=0;i<n;i++)	cin>>pre[i];

	BiTree root = build_Tree_from_PreIn(in,0,n-1,pre,0,n-1);

	//	print_pre(root);

	mirror(root);

	bfs(root);

	return 0;

}

同类题型

视频讲解

⬅️ L2-010 排座位 🏠 00-天梯赛 ➡️ L2-012 关于堆的判断